#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 019. 删除链表的倒数第 N 个结点.py
@time: 2022/1/15 12:57
@desc: https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
> 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

@解题思路：
    1. 找到倒数第k个（快、慢指针）
    2. 删掉
    3. t: O(L), s: O(1)
'''
# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        def remove(pre, node):
            pre.next = node.next
        if not head: return None
        pre, slow, fast = None, head, head
        for _ in range(n):
            fast = fast.next
        while fast:
            fast = fast.next
            pre = slow
            slow = slow.next
        # 被删元素是头节点的情况
        if not pre: head = slow.next
        else:
            remove(pre, slow)
        return head

class Solution2(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        画图理解：
            输入：head = [1,2,3,4,5], n = 2
            输出：[1,2,3,5]
        """
        if not head: return None
        dummy = ListNode(-1, next=head)
        slow, fast = dummy, dummy
        # 遍历n+1次就可以使slow停在被删节点的前一个结点
        for _ in range(n+1):
            fast = fast.next
        while fast:
            fast = fast.next
            slow = slow.next
        # 此时slow在被删节点之前，应当删除slow.next
        slow.next = slow.next.next
        return dummy.next